package Demo2;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class Solution3 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    ListNode head = null;
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();

        while(head1 != null) {
            stack1.add(head1.val);
            head1 = head1.next;
        }
        System.out.println();
        while(head2 != null) {
            stack2.add(head2.val);
            head2 = head2.next;
        }
        int tmp = 0;
        while(!stack1.isEmpty() && !stack2.isEmpty()) {
            int sum = stack1.pop() + stack2.pop() + tmp;
            tmp = sum / 10;
            addHead(sum % 10);
        }
        while(!stack1.isEmpty()) {
            int sum = stack1.pop() + tmp;
            tmp = sum / 10;
            addHead(sum % 10);
        }
        while(!stack2.isEmpty()) {
            int sum = stack2.pop() + tmp;
            tmp = sum / 10;
            addHead(sum % 10);
        }
        if(tmp > 0) addHead(tmp);
        return head;
    }

    // 头插法
    public void addHead(Integer val) {
        if(head == null) {
            head =  new ListNode(val);
            return ;
        }
        ListNode node = new ListNode(val);
        node.next = head;
        head = node;
    }
}
class Demo3 {
    public static void main(String[] args) {
        Solution3 solution3 = new Solution3();
        ListNode listNode1 = new ListNode(9);
        ListNode cur = listNode1;
        cur.next = new ListNode(3);
        cur = cur.next;
        cur.next = new ListNode(7);
        ListNode listNode2 = new ListNode(6);
        cur = listNode2;
        cur.next = new ListNode(3);
        ListNode listNode = solution3.addInList(listNode1, listNode2);
        System.out.println();
        while(listNode != null) {
            System.out.print(listNode.val + " ");
            listNode = listNode.next;
        }
    }
}